#include<vector>
using namespace std;
class Solution 
{
public:
    int uniquePaths(int m, int n) 
    {
        //最后一步一定从右下角的上方左边
        //此时的方案数就是二者之和
        //因此dp(i,j)就表示到（i，j）的方案数
        vector<vector<int>>dp(m,vector<int>(n,0));
        for(int i=0;i<n;i++) dp[0][i]=1;//第一行全部1
        for(int i=1;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
               if(i-1>=0) dp[i][j]+=dp[i-1][j];
               if(j-1>=0)dp[i][j]+=dp[i][j-1]; 
            }
        }
        return dp[m-1][n-1];
    }
};